An iterative method is a method that takes a initial starting point \({{x}^{(0)}}_{i}\) and computes the next values \({x}^{(1)}\), \({x}^{(2)}\) and so on, which are hoped to be increasingly better approximate solutions to the problem. This is done until reaching a stopping criterion. Common stopping criteria is number of steps or change in estimate is less than a threshold quantity.

The secant method is a root finding method. The secant method uses \({x}_{n-1}\) and \({x}_{n}\) to draw a line between two points that crudely approximates the function. We then solve for where the line crosses the x-axis, which is then the next \({x}_{n+1}\).

Gradient ascent computes the gradient at \({x}^{(t)}\). It will point in the direction of steepest ascent. We follow this direction to find the next \({x}^{(t+1)}\). Terminates when the gradient is \(0\) or negligibly small.

In Newton-like methods the Hessian is replaced by an approximation.

This is because the Hessian is expensive to compute, and there are many cheaper alternatives that can perform well.

Fisher scoring is a Newton-like method for maximizing a likelihood function where the Hessian stand-in is the negative Fisher information matrix, replacing the negative observed information \({-{\sum}_{i} {{\partial}_{\theta}}^{2} \ell(\theta\vert{x}_{i})}\).

In this method, we check if the score of the imminent \({x}^{a(i+1)}\) is greater than the previous score before it is accepted. If it is not accepted, we consider smaller and smaller steps towards \({x}^{(i+1)}\), until the score is improved.

A quasi-Newton method is a Newton-like method that uses the Hessian stand-in \({M}^{(t)}\) to generate the next step’s \({M}^{(t+1)}\). The Hessian stand-in is updated, rather than computed from scratch.

Davidon’s update method is a quasi-Newton method. It uses the gradient at \({x}^{(t)}\) and \({x}^{(t+1)}\) to compute

Davidon–Fletcher–Powell formula is a quasi-Newton method

Broyden–Fletcher–Goldfarb–Shanno algorithm is a quasi-Newton method

In \(n\)-dimensional space, use \(n+1\) vertices. The Nelder–Mead method gradually moves the simplex spanned by these vertices toward a maximum.

A variable selection method.

\[{f \to{} X \to{} Y = h(X)}\]
Let \(\mathcal{M}\) be a model with parameters \(\Theta\), let \({\ell(\theta\vertX)}\) be the log-likelihood function of the data.
What if some data is missing? Let \(Y\) be the available data and \(Z\) the missing data. The EM algorithm uses the available data Y and the immediate estimate \(\theta\). E-step: we have the log-likelihood which depends on \(\theta\), \(Y\) and \(Z\). We have \(Y\) and an approximation of \(\theta\), but not \(Z\). In this step we sum out \(Z\) to create a function \(Q\) of \(\theta\) and \(Y\) only. M-step: Maximize the function \(Q\) from the previous step to find a new estimate of the parameter \(\theta\).
Start with an estimate of \(\theta\).

\[{f \to{} X = (Y, Z) \to{} Y}\]
When there is a set of observed variables \({Y}_{{1:n}}\) and a set of unobserved/latent variables \({Z}_{{1:n}}\), the EM algorithm can be applied as follows.

For exponential distributions the EM algorithm...

A modification of the E step in the EM algorithm. At each step, we try to compute the unobserved information as well.

By resampling, for example bootstrap, we can run the EM algorithm several times for these pseudosamples. By these pseudosamples we can find a bootstrap estimate for the variance.

Calculating the expectation in \(Q\) could be difficult. This modification uses Monte Carlo to approximate the expectation.

Conditional maximization: place a constraint on the maximization step.

Replace the M-step with a single step with Newton’s method. Instead of maximizing, perform one step of Newton’s method. \[{{\theta}^{(t+1)} = {\theta}^{(t)} - \frac{{Q'(\theta\vert{\theta}^{(t)})}}{{Q''(\theta\vert{\theta}^{(t)})}}}\]

Modify the EM gradient to use a quasi-Newton method instead of a step of Newton’s method.

\[{{\theta}^{(t+1)} = {\theta}^{(t)} - \frac{.}{{\ell''{\left(#1\right)}}}}\]

A Monte Carlo method uses generated random samples (often from a uniform distribution) to produce random samples from a more complicated distribution.
Sometimes it is infeasible to integrate or normalize a distribution. This also means that we do not have access to its distribution nor likelihood function.

Monte Carlo simulation uses random sampling from a simple distribution to create a sample from a more complex distribution.

Monte Carlo estimation is a method for estimating a parameter of a distribution. Monte Carlo simulation is used to produce a sample from

Monte Carlo integration \(x\)

Inverse CDF sampling is a Monte Carlo sampling method. In inverse CDF sampling, random values are sampled from a uniform distribution on \({{\left[0..1\right]}}\). \({F}^{-1}\) is then applied to the sample values to obtain a sample over \(f\).
This means that a sample from any distribution can be obtained by sampling from a uniform distribution under the hood and knowing \({F}^{-1}\). Advantages of this is that implementing a uniform distribution sampler is simpler than most distributions.

If \(F\) is available but not \({F}^{-1}\), this sampling method can approximate the inverse by interpolation.
Overlay a grid of points \({{\left\{{{x}_{1}, {x}_{2}, \dots, {x}_{g}}\right\}}}\) on the support of \(F\). Compute \({{\left\{{{F}_{1}, {F}_{2}, \dots, {F}_{g}}\right\}}}\) and use this to interpolate the values from a random sample from a uniform distribution to obtain a sample from \(f\).

..

Rejection sampling (accept-reject sampling) is a Monte Carlo sampling method that generalizes the idea of uniform rejection sampling.

The envelope and squeezing function are iteratively refined every step as well.

Importance sampling A sampling method where we sample a weighted sample. This can lower the variance.

The crude Monte Carlo estimator has variance

Antithetic sampling is a modification of Monte Carlo sampling. If a

Let \(h\) be monotonic.
One way to implement antithetic sampling is to exploit the fact that \(h\) is monotonic. We can easily generate negatively correlated uniform variables, and monotonicity preserves this negative correlation when applied to the variables.
Sample from \(U\) to get \({X}_{i}\) and \({{Y}_{i} = 1 - {X}_{i}}\), two opposite values on \({{\left[0..1\right]}}\). \({X}_{i}\) and \({Y}_{i}\) are negatively correlated, and since \(h\) is monotonic, \({h({X}_{i})}\) and \({h({Y}_{i})}\) are as well.
The Monte Carlo estimator is \({{\hat\mu}_{\text{AS}} = {\sum}_{i} \frac{h(X_i) + h(Y_i)}{2}}\).

Control variates: the offset in a known quantity is correlated with the offset in the unknown quantity.

Implements control variates for importance sampling by using the weights as a control variate.

By the Rao–Blackwell theorem, conditioning an estimator of \(\theta\) on a sufficient statistic for \(\theta\) returns an estimator with smaller variance.
We have the Monte Carlo estimate \({\frac{1}{n} {\sum}_{i} h({X}_{i})}\) of \({{\operatorname{\mathbb{E}} f(X)}}\).

Wh

A method where instead of sampling from f, we sample from an envelope g of f.

We use the weighted sample

In sequential Monte Carlo the sample points themselves are generated in several steps.
Sequential Monte Carlo is useful when the sample points are high dimensional or sequences. The hope is that there is some structure within the sample points that makes them easier to sample stepwise. For example, a Markov chain or time series.

A sequential Monte Carlo method generates for each t a sample of time series.

A sequential Monte Carlo method generates a sample in step \(i\), and uses this sample to generate a sample in step \(i + 1\).

This method is cheap to update: we simply append a new observation to the time series and update the weigth.

In sequential Monte Carlo the sample points themselves are generated in several steps.
Sequential Monte Carlo is useful when the sample points are high dimensional or sequences. The hope is that there is some structure within the sample points that makes them easier to sample stepwise. For example, a Markov chain or time series.

A sequential Monte Carlo method generates for each t a sample of time series.

A sequential Monte Carlo method generates a sample in step \(i\), and uses this sample to generate a sample in step \(i + 1\).

This method is cheap to update: we simply append a new observation to the time series and update the weigth.

The sequential version of importance sampling.

Sequential importance sampling

1) Generate a weighted sample of n elements.

2) Loop:

When the process is a Markov process, sequential importance sampling is simplified.

In this method the envelope is updated at each t.

A particle filter is a sequential Monte Carlo method that has n sequences, X^(1), ..., X^(n). At each step a new observation is generated for and appended to each of the sequences.

At each step, a weighted sample is drawn. Then a resample is performed; this will prioritize.

This causes particles with low weights to be discarded, while high weight particles are replicated. The sampling step introduces variation between the particles.

Running the algorithm many steps should make the particles converge.

fn particle_filter(initial_vals, t) {
  n <- initial_vals.len()
  seqs <- []
  for i in 0..n {
    seqs[i] <- [initial_vals[i]]
  }
  for s in 0..t {

  }
}

(Not to be confused for sampling importance resampling)
Modifies sequential importance sampling. During the steps of sequential importance sampling, it is checked if the weights have become degenerate, for example by calculating the effective sample size and checking if it has fallen below a threshold. If so, the sequences generated so far are resampled according to their weights, and the method continues with those sequences. Their weights are reset to \(\frac{1}{n}\).

A bootstrap filter is a particle filter that resamples with replacement the sequences at the end of each step. The resampled sequences replaces the original ones, and their weights are set to \(\frac{1}{n}\).

Given a distribution f, the goal of the MCMC method is to create a Markov chain with stationary distribution f. We can then use the chain to draw a sample.

In Metropolis–Hastings, a proposal distribution is used to draw. We

When the proposal is symmetric, for example when it is a normal distribution, then the MH ratio reduces to \(\frac{f(x^*)}{{f({x}^{(t)})}}\)

In Gibbs sampling, we assume that we can sa

...

Gibbs sampling where in each cycle we update blocks of variables in different ways.

...

Let X be a sample. A resampling method generates pseudosamples using only X.

A bootstrapping method is a resampling method that produces bootstrap pseudosamples.

A permutation test is a test for the null hypothesis: both distributions are the same.

A bootstrapping method is a resampling method that produces bootstrap pseudosamples.

In exhaustive bootstrapping, we iterate over all possible bootstrap samples, evaluate \(T(X)\) and generate the exact histogram for \(T(X)\).

However, the number of possible bootstrap samples, \({n}^{n}\), quickly blows up, so this method is infeasible; instead, we approximate by randomly sampling for example \(10 000\) bootstrap samples.

Regular bootstrapping. Resample with replacement

Let \({f(x \vert{} \theta)}\) be a parametric distribution and \(X\) a sample from \(f\).

In parametric bootstrapping, we use the available sample to estimate the parameter of the distribution, and then draw pseudosamples from the estimated distribution.

We can now draw pseudo-samples from \({f(x \vert{} \theta)}\).

Method for bootstrapping a realized regression model.

Bootstrapping a regression model we want to find the distribution of \(\beta\), the regression parameter.

...

The percentile method is a method for constructing a confidence interval for \(\theta\) based on the histogram for \(\hat\theta\) produced by bootstrapping.

A test based on the percentile method. The test rejects the null hypothesis \({{H}_{O} = {x}_{0}}\) if \({x}_{0}\) is outside the bootstrap confidence interval.

Pivoting is a method to produce confidence intervals through using a pivotal quantity.

A pivoting method for generating a confidence interval for a parameter, but where the bias of the endpoints of the confidence interval are corrected.

More robust than simple percentile method:

We find functions and parameters to transform the bias to a standard normal distributed. The bootstrap principle gives the bootstrap estimator a StdN distribution.

We can now use the quantiles of the StdN

...

...

Bias reducing bootstrap methods

Balanced bootstrap is a way to bootstrap without introducing any bias. We do this by making sure that

1) Concatenate B copies of the sample. This ensures that the frequency of all sample elements are preserved. 2) Randomly permute the concatenation. 3) Read off the B bootstrap samples.

Antithetic bootstrapping is a way to eliminate bias.

Impose ordering on the sample by ordering statistics. When drawing a sample, also draw a sample from the reversed indices. This creates two negatively correlated pseudosamples.

If we know the model, we can resample residuals. We will then get a pseudosample this way.

When bootstrapping time series, we must try to preserve autocorrelation.

To preserve the autocorrelation between observations, we sample blocks of observations from the sample in place of singular observations.

All sequences of k consequtive observations are considered a block. Thus we can start from any index (except near the end).

This is a nested form of block bootstrapping. We perform block bootstrapping on the original sample, then we